package com.shuang.backtracking11;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Permute {
//    ///方法一：标记数组
//    class Solution {
//        //全局变量
//        List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
//        LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
//
//        public List<List<Integer>> permute(int[] nums) {
//
//            //定义标记数组 用来记录path中已经存过的值 避免重复取值
//            boolean[] used = new boolean[nums.length];
//            Arrays.fill(used, false);
//
//            backTracking(nums, used);
//
//            return result;
//        }
//
//        private void backTracking(int[] nums, boolean[] used){
//
//            //终止条件
//            if (path.size() == nums.length){
//                result.add(new ArrayList(path));
//                return;
//            }
//
//            //for 排列问题 直接从零开始
//            for (int i = 0; i < nums.length; i++){
//                //path中取过该值的话直接跳过本次循环
//                if (used[i]){
//                    continue;
//                }
//
//                //取值
//                path.add(nums[i]);
//                used[i] = true; //当前位置的值取过将used其位置设为true 记录
//
//                //递归
//                backTracking(nums, used);
//
//                //回溯
//                path.removeLast();
//                used[i] = false;
//            }
//        }
//    }

    //方法二：通过判断path中是否存在数字，排除已经选择的数字
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0)
            return result;
        backtrack(nums);
        return result;
    }

    public void backtrack(int[] nums) {

        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 如果path中已有，则跳过
            if (path.contains(nums[i])) {
                continue;
            }
            path.add(nums[i]);
            backtrack(nums);
            path.removeLast();
        }
    }
}
